package ninthDay;

public class Flatten {
    public Node flatten(Node head) {
        dfs(head);
        return head;
    }
    public Node dfs(Node head){
        Node end = head;
        while (head != null){
            if (head.child == null){
                end = head;
                head = head.next;
            }else {
                Node temp = head.next;
                Node childN = dfs(head.child);
                head.next = head.child;
                head.child.prev = head;
                head.child = null;
                childN.next = temp;
                if (temp != null){
                    temp.prev = childN;
                }
                end = head;
                head = childN;
            }
        }
        return end;
    }
}
